package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class Client {

    @Test
    public void testBinaryTree() {

        BinaryTree binaryTree = new BinaryTree();

        Node node1 = new Node(1, "张三");
        Node node2 = new Node(2, "李四");
        Node node3 = new Node(3, "王五");
        Node node4 = new Node(4, "赵六");
        Node node5 = new Node(5, "朱七");
        Node node6 = new Node(6, "郭八");

//        binaryTree.setRoot(node1);
//        node1.setLeft(node2);
//        node1.setRight(node3);
//        node2.setRight(node4);
//        node3.setRight(node5);
//        node5.setLeft(node6);

        binaryTree.add(node3);
        binaryTree.add(node1);
        binaryTree.add(node6);
        binaryTree.add(node4);
        binaryTree.add(node5);
        binaryTree.add(node2);

        System.out.println("前序遍历：");
        binaryTree.preorderTraversal();
        System.out.println("中序遍历：");
        binaryTree.inorderTraversal();
        System.out.println("后序遍历：");
        binaryTree.postorderTraversal();

        System.out.println("-----------------------------------");

        System.out.println("前序查找：");
        binaryTree.preorderSearch(6);
        System.out.println("中序查找：");
        binaryTree.inorderSearch(6);
        System.out.println("后序查找：");
        binaryTree.postorderSearch(6);

        System.out.println("-----------------------------------");

        System.out.println("删除前：");
        binaryTree.preorderTraversal();
        binaryTree.delete(2);
        System.out.println("删除后：");
        binaryTree.preorderTraversal();
    }

    @Test
    public void testSequentialStorageBinaryTree() {

        SequentialNode[] nodes = new SequentialNode[10];

        for (int i = 0; i < nodes.length; i++) {

            nodes[i] = new SequentialNode(i + 1, "王芳" + i);
        }

        SequentialStorageBinaryTree sequentialStorageBinaryTree = new SequentialStorageBinaryTree(nodes);

        System.out.println("前序遍历：");
        sequentialStorageBinaryTree.preorderTraversal();

        System.out.println("中序遍历：");
        sequentialStorageBinaryTree.inorderTraversal();

        System.out.println("后序遍历：");
        sequentialStorageBinaryTree.postorderTraversal();

    }

    @Test
    public void testInorderThreadedBinaryTree() {

        ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();

        ThreadedNode node1 = new ThreadedNode(1, "张三");
        ThreadedNode node2 = new ThreadedNode(2, "李四");
        ThreadedNode node3 = new ThreadedNode(3, "王五");
        ThreadedNode node4 = new ThreadedNode(4, "赵六");
        ThreadedNode node5 = new ThreadedNode(5, "朱七");
        ThreadedNode node6 = new ThreadedNode(6, "郭八");

        binaryTree.add(node3);
        binaryTree.add(node1);
        binaryTree.add(node6);
        binaryTree.add(node4);
        binaryTree.add(node5);
        binaryTree.add(node2);

        binaryTree.inorderThreadNodes();

        System.out.println("node2的前驱节点" + node2.getLeft());
        System.out.println("node2的后驱节点" + node2.getRight());

        System.out.println("遍历中序线索化二叉树:");

        binaryTree.inorderThreadedList();
    }

    @Test
    public void testpreorderThreadedBinaryTree() {

        ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();

        ThreadedNode node1 = new ThreadedNode(1, "张三");
        ThreadedNode node2 = new ThreadedNode(2, "李四");
        ThreadedNode node3 = new ThreadedNode(3, "王五");
        ThreadedNode node4 = new ThreadedNode(4, "赵六");
        ThreadedNode node5 = new ThreadedNode(5, "朱七");
        ThreadedNode node6 = new ThreadedNode(6, "郭八");

        binaryTree.add(node3);
        binaryTree.add(node1);
        binaryTree.add(node6);
        binaryTree.add(node4);
        binaryTree.add(node5);
        binaryTree.add(node2);

        binaryTree.preorderThreadedNodes();

        System.out.println("node2的前驱节点" + node2.getLeft());
        System.out.println("node2的后驱节点" + node2.getRight());

        System.out.println("遍历前序线索化二叉树:");

        binaryTree.preorderThreadedList();
    }

    @Test
    public void testpostorderThreadedBinaryTree() {

        ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();

        ThreadedNode node1 = new ThreadedNode(1, "张三");
        ThreadedNode node2 = new ThreadedNode(2, "李四");
        ThreadedNode node3 = new ThreadedNode(3, "王五");
        ThreadedNode node4 = new ThreadedNode(4, "赵六");
        ThreadedNode node5 = new ThreadedNode(5, "朱七");
        ThreadedNode node6 = new ThreadedNode(6, "郭八");

        binaryTree.add(node3);
        binaryTree.add(node1);
        binaryTree.add(node6);
        binaryTree.add(node4);
        binaryTree.add(node5);
        binaryTree.add(node2);

        binaryTree.postorderThreadedNodes();

        System.out.println("node2的前驱节点" + node2.getLeft());
        System.out.println("node2的后驱节点" + node2.getRight());

        System.out.println("遍历后序线索化二叉树:");

        binaryTree.postorderThreadedList();
    }

    @Test
    public void testHuffmanTree() {

        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100);
        }

        HuffmanTree huffmanTree = new HuffmanTree(arr);

        huffmanTree.preorderTransversal();
    }

    @Test
    public void testHuffmanCode() {

        HuffmanCode huffmanCode = new HuffmanCode("A: do you like java? B: yes, I do. A: ha ha ha ha~~~ B: xi xi xi xi~~~");

        System.out.println("哈夫曼树前序遍历：");
        huffmanCode.getHuffmanCodeTree().preorderTransversal();

        System.out.println("哈夫曼编码表：\n" + huffmanCode.getHuffmanCodeTable());

        System.out.println("哈夫曼编码：\n" + huffmanCode.getHuffmanCode());
        System.out.println("哈夫曼编码长度：" + huffmanCode.getHuffmanCode().length());

        System.out.println("译码结果：\n" + huffmanCode.decode());
    }


    // 重复字多的时候压缩明显。
    @Test
    public void testZipFile(){

        String srcFile = "src\\main\\java\\cn\\cxq\\learning\\file\\a.txt"; //源文件
        String dstFile = "src\\main\\java\\cn\\cxq\\learning\\file\\a.zip"; //目标文件
        String dstFile2 = "src\\main\\java\\cn\\cxq\\learning\\file\\b.txt"; //解压目标文件

//        String srcFile = "src\\main\\java\\cn\\cxq\\learning\\file\\sample01.jpg"; //源文件
//        String dstFile = "src\\main\\java\\cn\\cxq\\learning\\file\\sample01.zip"; //目标文件
//        String dstFile2 = "src\\main\\java\\cn\\cxq\\learning\\file\\sample02.jpg"; //解压目标文件

        HuffmanCode huffmanCode = new HuffmanCode();

        huffmanCode.zipFile(srcFile,dstFile);

        huffmanCode.unZipFile(dstFile,dstFile2);
    }

    @Test
    public void testBinarySortTree(){

        BinarySortTree binarySortTree = new BinarySortTree();

        binarySortTree.add(new BinarySortNode(33));
        binarySortTree.add(new BinarySortNode(25));
        binarySortTree.add(new BinarySortNode(7));
        binarySortTree.add(new BinarySortNode(7));
        binarySortTree.add(new BinarySortNode(12));
        binarySortTree.add(new BinarySortNode(10));
        binarySortTree.add(new BinarySortNode(66));
        binarySortTree.add(new BinarySortNode(100));
        binarySortTree.add(new BinarySortNode(50));
        binarySortTree.add(new BinarySortNode(100));
        binarySortTree.add(new BinarySortNode(20));
        binarySortTree.add(new BinarySortNode(3));

        binarySortTree.inorderTransversal();

        System.out.println("-----------------------------------------------");

        System.out.println(binarySortTree.search(12));
        System.out.println(binarySortTree.searchParent(12));

        System.out.println("-----------------------------------------------");

        binarySortTree.delete(100);
        binarySortTree.inorderTransversal();

        System.out.println("-----------------------------------------------");

        binarySortTree.delete(10);
        binarySortTree.inorderTransversal();

        System.out.println("-----------------------------------------------");

        binarySortTree.delete(7);
        binarySortTree.inorderTransversal();

        System.out.println("-----------------------------------------------");

        binarySortTree.delete(25);
        binarySortTree.inorderTransversal();

        System.out.println("-----------------------------------------------");

        binarySortTree.delete(66);
        binarySortTree.inorderTransversal();
    }

    /**
     * 平衡二叉树：
     *             3                                      4                                    4                                        6                                       6
     *           /  \                        |\         /  \                       |\        /  \                           |\        /  \                          |\        /   \
     *          1    6    -------------------  \       3    6   -------------------  \      3    6       -------------------  \      4   10      -------------------  \     4      50
     *             /  \   -------------------  /     /    /  \  -------------------  /         /  \      -------------------  /       \          -------------------  /      \    /  \
     *            4   10                    |/      1    5   10                   |/          5   10                       |/          5                           |/         5  10 100
     *             \                                                                                                                                                                 /
     *              5                                                                                                                                                              60
     */
    @Test
    public void testAvervageBinarySortTree(){
        AverageBinarySortTree averageBinarySortTree = new AverageBinarySortTree();

        averageBinarySortTree.add(new AverageBinarySortNode(3));
        averageBinarySortTree.add(new AverageBinarySortNode(6));
        averageBinarySortTree.add(new AverageBinarySortNode(1));
        averageBinarySortTree.add(new AverageBinarySortNode(10));
        averageBinarySortTree.add(new AverageBinarySortNode(4));
        averageBinarySortTree.add(new AverageBinarySortNode(5));



        averageBinarySortTree.inorderTransversal();

        System.out.println("根节点左子树高度：" + averageBinarySortTree.getRoot().leftHeight());
        System.out.println("根节点右子树高度：" + averageBinarySortTree.getRoot().rightHeight());

        System.out.println(averageBinarySortTree.search(6).left); // 5
        System.out.println(averageBinarySortTree.search(6).right); // 10

        System.out.println("------------------------------------------------------------");

        averageBinarySortTree.delete(1);
        averageBinarySortTree.delete(3);

        averageBinarySortTree.inorderTransversal();

        System.out.println("根节点左子树高度：" + averageBinarySortTree.getRoot().leftHeight());
        System.out.println("根节点右子树高度：" + averageBinarySortTree.getRoot().rightHeight());

        System.out.println(averageBinarySortTree.search(6).left); // 4
        System.out.println(averageBinarySortTree.search(6).right); // 10

        System.out.println("------------------------------------------------------------");

        averageBinarySortTree.add(new AverageBinarySortNode(100));
        averageBinarySortTree.add(new AverageBinarySortNode(50));
        averageBinarySortTree.add(new AverageBinarySortNode(60));

        averageBinarySortTree.inorderTransversal();

        System.out.println("根节点左子树高度：" + averageBinarySortTree.getRoot().leftHeight());
        System.out.println("根节点右子树高度：" + averageBinarySortTree.getRoot().rightHeight());

        System.out.println(averageBinarySortTree.search(6).left); // 4
        System.out.println(averageBinarySortTree.search(6).right); // 10
    }
}
